package algorithm.algorithm4.sort;

import java.util.ArrayList;
import java.util.List;

import edu.princeton.cs.algs4.StdRandom;
import edu.princeton.cs.algs4.Stopwatch;

public class SortUtils {
	public static <T> void swap(List<T> arr,int i,int j)
	{
		T tmp=arr.get(i);
		arr.set(i, arr.get(j));
		arr.set(j,tmp);
	}
	public static <T> void sop(List<T> arr) 
	{
		for(T item:arr)
			System.out.print(item+" ");
		System.out.println();
	}
	public static List<Integer> rand_nums(int n)
	{//随机产生数组数据
		List<Integer> res = new ArrayList<>();
		for(int i=0;i<n;i++)
			res.add(StdRandom.uniform(100));
		return res;
	}
	private static <E extends Comparable<E>> void select_algorithm(String algo,List<E> arr) throws Exception
	{
		if(algo.equals("insert"))	Sort.insert_sort(arr);
		else if(algo.equals("select"))	Sort.select_sort(arr);
		else if(algo.equals("insert_ex"))	Sort.insert_sort_ex(arr);
		else if(algo.equals("shell"))	Sort.shell_sort(arr);
		else if(algo.equals("guibing"))	Sort.guibing_sort(arr);
		else if(algo.equals("guibing_bu"))	Sort.guibing_sort_BU(arr);
		else if(algo.equals("quick"))	Sort.quick_sort(arr);
		else if(algo.equals("quick_3way"))	Sort.quick_sort_3way(arr);
		else {
			throw new Exception("illegal input:"+algo);
		}
	}
	public static void test(String algo,int size)
	{
		List<Integer> arr = new ArrayList<>();
		for(int i=0;i<size;i++)
			arr.add(StdRandom.uniform(100));
		System.out.println(algo+" before sort : ");
		sop(arr);
		try {
			select_algorithm(algo, arr);
		} catch (Exception e) {
			System.out.println(e.toString());
			System.out.println("Please input available algorithm.");
		}
		System.out.println(algo+" after sort:");
		sop(arr);
		for(int i=0;i<arr.size()-1;i++)
			if(arr.get(i)>arr.get(i+1))
			{
				System.out.println("Oh,no.The array is not ordered.");
				return;
			}
		System.out.println("Yes!The array is ordered!");
	}
	private static <E extends Comparable<E>> double time(String algo,List<E> arr)
	{
		Stopwatch timer = new Stopwatch();
		try {
			select_algorithm(algo, arr);
		} catch (Exception e) {
			System.out.println("Please input available algorithm.");
		}
		return timer.elapsedTime();
	}
	public static double time_random_input(String algo,int size,int T,int max)
	{
		double total=0;
		List<Integer> arr = new ArrayList<>();
		for(int t=0;t<T;t++)
		{
			for(int i=0;i<size;i++)
				arr.add(StdRandom.uniform(max));
			total+=time(algo, arr);
		}
		return total;
	}
	public static void performance(int size, int T)
	{
		int max=1000;
		double total;
		String algo;
		System.out.println("Array size is "+size+",Run "+T+" times.");
		
//		algo="select";
//		total=time_random_input(algo, size, T, max);
//		System.out.format("%-10s:%f s.%n",algo,total);
//		algo="insert";
//		total=time_random_input(algo, size, T, max);
//		System.out.format("%-10s:%f s.%n",algo,total);
//		algo="insert_ex";
//		total=time_random_input(algo, size, T, max);
//		System.out.format("%-10s:%f s.%n",algo,total);
		algo="shell";
		total=time_random_input(algo, size, T, max);
		System.out.format("%-10s:%f s.%n",algo,total);
		algo="guibing";
		total=time_random_input(algo, size, T, max);
		System.out.format("%-10s:%f s.%n",algo,total);
		algo="guibing_bu";
		total=time_random_input(algo, size, T, max);
		System.out.format("%-10s:%f s.%n",algo,total);
		algo="quick";
		total=time_random_input(algo, size, T, max);
		System.out.format("%-10s:%f s.%n",algo,total);
		algo="quick_3way";
		total=time_random_input(algo, size, T, max);
		System.out.format("%-10s:%f s.%n",algo,total);
	}
}
